package 动态规划;

/**
 * 给定一个数组，不能取两个下标相邻的元素，求能取出的最大值
 * 例如{1,3,5,7,5};要么取1，5，5 要么取3,7
 *
 * 递归思路：
 *  假如数组nums长度为 n
 *  我们要求 长度为n时，这个数组能取出的最大值f(n)
 *  f(n)无法直接给出答案 但如果 能知道 f(n-1)和 f(n-2)的值，那么f(n)就能通过比较 f(n-1)和f(n-2)+nums[n]来的得出f(n)的结果
 *  f(n-1)也无法直接给出答案，需要知道 f(n-2)和 f(n-3)的值，那么f(n-1)就能通过比较f(n-2)和f(n-3)+nums[n-1]来得出f(n-1)的结果
 *  f(...)...
 *  直到 n=0时（f(0)），f(n)终于不需要知道f(n-1)的值了，因为只有一个数时，没有筛选的条件,我们可以直接返回nums[0]
 *  然后一层一层闭环，得出我们最初求的f(n)的值
 *
 * 缺点：
 *  通过上面的分析，我们知道 在f(n)时要求 f(n-2)的值 在f(n-1)时也要求f(n-2)的值，而且因为f(n-2)还需要往下递归，这样就需要求很多重复的递归
 */
public class Ch01_打家劫舍递归 {
    public static void main(String[] args) {
        int[] nums={1,3,5,7,5};
        System.out.println(maxMoney(nums,nums.length-1));
    }

    public static int maxMoney(int[] nums,int index){
        if (index<0){
            return 0;
        }
        if (index==0){
            return nums[0];
        }
        int curr=nums[index]+maxMoney(nums,index-2);
        int pre=maxMoney(nums,index-1);
        return curr>pre?curr:pre;
    }
}
